package simple;

/**
 * 给你一个非负整数 x ，计算并返回x的 算术平方根 。
 *
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 *
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 ** 链接：https://leetcode-cn.com/problems/sqrtx
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class Sqrtx {
    /**
     * 19:30 ~ 19:52  22min
     * 对于一个数x的平方根q，因为q去掉了小数部分。 则有q*q <= x
     * */
    class Solution {
        public int mySqrt(int x) {
            int l = 0;
            int r = x;
            int ans = -1;
            while(l < r){
                int mid = l + (r-l)/2;
                if((long) mid * (long) mid > x){
                    r = mid - 1;
                }else{
                    ans = mid;
                    l = mid + 1;
                }
            }
            return ans;
        }
    }
}
